package chapter15;

import java.util.Arrays;
import java.util.List;

/**
 * 动态规划-矩阵链乘法
 */
public class MatrixMultiply {

    public static int[][] matrixMultiply(int[][] A, int[][] B) {
        if (A[0].length != B.length) {
            return new int[][]{};
        }
        int[][] C = new int[A.length][B[0].length];
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B[0].length; j++) {
                for (int k = 1; k < A.length; k++) {
                    C[i][j] = C[i][j] + A[i][k] + B[k][j];
                }
            }
        }
        return C;
    }

    public static List<int[][]> matrixChainOrder(int[] p) {
        int n = p.length - 1;
        int[][] m = new int[n + 1][n + 1];
        int[][] s = new int[n + 1][n + 1];

        for (int l = 2; l <= n; l++) {
            for (int i = 1; i <= n - l + 1; i++) {
                int j = i + l - 1;
                m[i][j] = Integer.MAX_VALUE;
                for (int k = i; k <= j - 1; k++) {
                    int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                    if (q < m[i][j]) {
                        m[i][j] = q;
                        s[i][j] = k;
                    }
                }
            }
        }
        System.out.println(Arrays.deepToString(m));
        return List.of(m, s);
    }

    public static void printOptimalParens(int[][] s, int i, int j) {
        if (i == j) {
            System.out.print("A" + i);
        } else {
            System.out.print("(");
            printOptimalParens(s, i, s[i][j]);
            printOptimalParens(s, s[i][j] + 1, j);
            System.out.print(")");
        }
    }

    public static void printMatrixChainOrder(int[] p) {
        List<int[][]> res = matrixChainOrder(p);
        System.out.println("pmc->" + res.get(0)[res.get(0).length - 1][res.get(0)[0].length - 1]);
        printOptimalParens(res.get(1), 0, res.get(1).length - 1);
        // [0, 0, 0, 0, 0, 0]
        // [0, 0, 15750, 7875, 9375, 11875]
        // [0, 0, 0, 2625, 4375, 7125]
        // [0, 0, 0, 0, 750, 2500]
        // [0, 0, 0, 0, 0, 1000]
        // [0, 0, 0, 0, 0, 0]
    }


}
